Geocoding is a known technique whereby a human referencing system for physical locations, such as a street address, country and/or postcode is converted into associated geographic coordinates, e.g. latitude and longitude. Various different geocoding systems currently exist and rely, at least to some extent, on a geographic information system (GIS) in which the street network is already mapped within the geographic coordinate space. Inverse geocoding is the reverse process.
Any modern digital map (or mathematical graph, as they are sometimes known) can be considered as a GIS, and in a most simple form is effectively a database consisting of a plurality of tables defining firstly nodes (which can be considered as points or zero-dimensional objects) most commonly representative of road intersections, and secondly lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length or a looped segment (in which case the segment has a non-zero length), but are more commonly separate. Nodes may be considered real or “valid” for the purposes of this application when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas “artificial” or “avoidable” nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road.
In this manner, nodes, lines and segments can be used as a means of completely describing a road network, and each element in the database is further defined by various attributes which are again represented by data in the tables of the database, e.g. each node will typically have latitude and longitude attributes to define its real-world position. The complete “graph” of the road network is described by millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.
Although practically all modern digital maps involve a structured definition of nodes and segments, the actual manner in which this is effected between digital map providers varies enormously. For instance, each map vendor (and possibly each map version) may use unique Ds for each map element, whether node or segment. Therefore, even simple geocoding and inverse geocoding is possible only with some knowledge of the underlying structure of the database in which the requisite digital map is embodied. More simply, a query designed to extract a street address from one digital map database based on latitude and longitude will not necessarily work on another—it may need re-casting as appropriate for the particular digital map database in question. This can also be true for different versions of a digital map provided by the same vendor.
To overcome the drawbacks associated with map-specific referencing, a map agnostic location referencing system has been developed by TomTom International B.V., which is referred to as OpenLR™. An example of encoding of a location using OpenLR™ is described in WO 2010/000707, while the associated decoding of a location encoded using OpenLR™ is described in WO 2010/000706. Further details of the OpenLR™ location referencing system can be found in the documents found at http://www.openlr.org.
The input to an OpenLR encoder is a route or path (also referred to as a “line location”—a connected path of line elements in a road network having exactly one start/end point) and a map database (e.g. MapA), which provides the road network the route is located in. The output is a map-independent line location reference. A “line location reference” as used herein means a set of information, typically map-independent, relating to a line location. On a receiving side an OpenLR decoder finds back the original route based on this line location reference and a map database (e.g. MapB) that covers the relevant road network. MapA and MapB do not need to refer to the same map database as long as they cover the same geographic area.
The manner by which a location is conventionally encoded using OpenLR™, i.e. as set out in WO 2010/000707, will now be described. The following description is provided in terms of segments, but it is to be understood that the method can be equally applied to lines, or to combinations of lines and segments, which together are representative of a continuous path through a road network.
Referring firstly to FIG. 1, and as previously mentioned, it is possible to store complete location references having previously been successfully encoded according to the present invention in a database, and therefore in FIG. 1 at step 10, a check is made of such database to establish whether the location desired to be encoded has already been encoded. If so, then the previously encoded location can be retrieved from the database, without any further processing.
If the location is not present in the database, then a validity check 14 is performed on the location and its constituent segments to determine whether the location meets certain criteria hereinafter described, and provided that the location is valid, the location reference is created at step 16. If either the validity check, or the creation of a location reference for that particular location fails, then such failure may also be stored in said database as indicated in step 18.
As final steps in the process, the location reference created at 16 is further checked for validity in step 20. Step 22 is illustrative in that it signifies conversion from one representation to another. Ultimately, the conversion process (which may include one or more intermediate formats) results in a wirelessly transmissible and machine readable binary representation as prescribed in a physical data format such as that hereinafter described. This format may take another form, such as XML or indeed any other mark-up or machine-readable representation useful in transferring information between an encoder and decoder, and the present invention is not to be considered limited to the specific format described. Thereafter, the complete, accurate and correct representation of the location can be stored in said database, as indicated in step 24.
Referring to FIG. 2, the “Check_Location” validity check process illustrated at 14 in FIG. 1 is further described. All locations which are not stored in the database of previously encoded locations need to be checked for validity before further processing. As a first step, at 30, a connectivity check is performed. The check of the connectivity ensures that the incoming location is not split up into two or more different stretches which are not connected. Each connected stretch needs to be handled separately and represents one location to be encoded in its own right. This check is passed if the location consists of only one connected stretch.
At step 32, a functional road class check is performed. This check ensures that all of the segments forming part of the initial location meet a minimum functional road class as defined in the underlying digital map. The functional road class (FRC) is a common attribute of lines or segments in map data and indicative of a relative importance of a particular type of road. An arbitrary decision to include only functional road classes from 0-7 has been made, as this effectively precludes any non-navigable roads, or roads of a very low category on which traffic events would be most unlikely ever to occur. The greater the FRC value, the relatively less important is the road. Within the range of functional road classes used herein an FRC of 0 indicates a functional road class of highest importance and an FRC of 7 a functional road class of lowest importance
In one embodiment, the encoder can be enabled to check whether the location is affected by turn restrictions or not. If enabled, then the location will be investigated step by step, as indicated at 34, if there is a turn restriction along the way. Every turn from segment to segment needs to be valid. If not, an exception will be thrown at 39 and the location will not be encoded. It is worth mentioning here that the turn restriction check need not be enabled, and the method will continue to encode locations successfully for the vast majority of locations. However enabling a turn restriction check as described merely acts as an extra means of ensuring successful encoding.
As final steps to the validity check of the location, a determination is made as to whether the start node of the first segment in the location and the end node of the last segment in the location are real nodes, as opposed to being artificial or avoidable nodes. To explain further, segments in most instances tend to be artificial constructions and arbitrarily defined by the map vendor. Nevertheless they do provide much greater resolution compared to lines as regards describing traffic events on real-world sections of road where the traffic event begins at some arbitrary point along a particular road section. In the context of a motorway or major highway, a traffic event may occur at some point between two intersections (represented by real nodes) located a significant distance apart (e.g. 15 km or more), and therefore the exact point at which a traffic situation exists is much more likely to be close to an artificial node than it is to a real node. However, the probability of having such artificial nodes in the decoder map is very small, so these artificial nodes are to be avoided. This is done by extending the location uniquely at its start and end to real nodes appearing in the underlying digital map, and an offset distance value is provided as an attribute to such nodes so that the exact position of the traffic (or other) event, i.e. the correct start of the location to be encoded, can be correctly referenced. Therefore, the location can be described precisely by using a path which covers the location completely and offsets. Having a longer path covering the location also allows for the possibility of re-using the location reference path and merely updating the offsets, which will save bandwidth and time.
Accordingly, if the start node is not artificial then there will be no extension. Otherwise the incoming segment to the first segment having the artificial start node is chosen as the new start segment at step 36. If the start node of the new start segment is also artificial or avoidable then the procedure is repeated until a suitable start node is identified.
The second step 38 tries to extend the end of the location. This is done in much the same way as for the start segment except that the end node of the last segment is assessed, and a search made for outgoing road segments. If in either of these two steps, an artificial node cannot be extended and a real node found, then it is possible to continue with the method using the artificial node in the hope that it can be matched on the decoding side. Accordingly, the method is still valid, but the confidence level is lower.
Referring to FIG. 3, a description of the Create_LocationReference step 16 in FIG. 1 is provided. After the validity processing described above, a valid sequence of segments is provided, and this is desired to be converted into a location reference as a tree of objects defined in a logical data format, as hereinafter described.
The first step 40 in the generation of a location reference according to the present invention is to identify the first segment at which the route search should commence.
Thereafter, a route search is performed at step 42 using either the first segment or an intermediate or deviation segment. The route search is a shortest path route calculation between the first (or intermediate) segment and last segment of the location. The specifics of route search are described in greater detail with reference to FIG. 4.
The route search calculates a shortest path between the start segment and the destination segment. This calculation is done iteratively, and after an initialization at step 50, the main loop including steps 52, 54, 56, 58 will calculate a shortest path. The shortest route path will be checked every iteration at step 56 (described in greater detail hereinafter with reference to FIG. 5) to establish whether the location is still part of the calculated shortest-path tree or not. If the location is not covered by the shortest-path tree anymore then the route calculation stops and returns a partial route (the part of the location which is covered so far) at step 60 and a segment which shall be used as intermediate location reference point to make the route search unique, and capable of being continued thereafter. This intermediate segment is identified at step 44 in FIG. 3 and returned to the route search algorithm as the new start segment from which one or more further route searches are to be conducted.
Ideally the route search will focus on the part of the location which is not extended as described above as the extended parts of the location will not have any influence on the route calculation because there is no deviation from this path possible. The extensions may be added to the location reference in a later step.
At step 50, the route search is initialized and all data structures are reset. At step 52, and decision point 53, a check is made as to whether the route search must be continued or can be stopped. The search can be stopped if:                the shortest-path between the start segment and destination segment is found, in which case a shortest path route can be generated as indicated at 62,        there are no more segments to process which means that there exists no route between the start segment and destination segment, as indicated at 64, or        if an intermediate segment is identified.        
In all practical cases, a route should always exist because the path itself is valid and forms such a route but this check is compulsory for every route search algorithm. In the case that the search is not complete, at step 54, the Get Next Line procedure fetches the best line from what is often called an “open-list” being a list of all those lines forming part of the shortest path between two relevant nodes. As a consequence of the shortest path algorithm, the shortest path to a line is finalised with the departure of a line forming part of the location from one being present in the open-list as retrieved at step 54. Accordingly, The “Check_Location_Coverage” step 56 is outlined in greater detail with reference to FIG. 5, but briefly this step checks if this condition is fulfilled during the route calculation. Checking during the route calculation means that every fixed segment (a segment is fixed if the shortest path thereto has been finally determined) will be investigated if it also forms part of the location. If the segment currently under consideration forms part of the location desired to be referenced, then a check is made to establish that the beginning part of the location is completely included in the current shortest-path tree. This means that the calculated shortest path to the last location segment needs to be the location itself. If any deviation is encountered, the route calculation is stopped and a partial route is generated at step 60 and returned to the route search process illustrated in FIG. 3. In step 44 of this figure, an intermediate segment is identified in the underlying digital map, and route search is re-started using this intermediate segment as the start point.
There are various different possibilities for correctly identifying and referencing the intermediate segment depending on the nature of the deviation which appears in the shortest path calculation, and these are all described with reference to FIGS. 5, 6, 7, and 8.
To check coincidence of the shortest path thus far determined, the last segment found on the location during the route search is stored in a route search list (indicated at 70 in FIG. 5) so that it can easily be determined which segment should come next, as only subsequent segments contiguous with the last stored segment, or at least having coinciding end and start nodes respectively, can be considered. It is fundamental to the economy of location reference length that the shortest path route search effectively eliminates those segments from the reference which fall on the shortest path, i.e. there is no need for them to form part of the reference. Accordingly, at decision points 72, 74, checks are made that the most recent segment forming part of a shortest path route list both exists or coincides with the location being encoded, and is correctly referenced as far as the shortest path is concerned in terms of pointers which are ideally used in the shortest path list to refer to:                the next expected segment on the shortest path, and        the previous segment on said shortest path.        
Provided that both these pointers reference segments which are also on the location path, then the location is considered precisely covered by the shortest path and the route search can continue.
Of course however, shorter deviations will inevitably be found, and all possible deviation types are covered by the various branches of the flowchart of FIG. 5, and the simple line drawings of FIGS. 6, 7, and 8. Most simply, a deviation is found if a segment on the location path is currently being analysed but this segment is at odds with the next expected segment as far as the shortest route list is concerned. A deviation is also found if the next expected segment of the shortest route list is in conformity with the next segment in the location path list, but the predecessor pointer for this segment in the shortest path list does not point to the location. This means that the predecessor pointer needs to be equal to the last segment found on location. In both cases it is necessary to identify a proper intermediate. The following steps determine this intermediate and in a special case it is necessary to add two intermediates. The main focus on finding a proper intermediate is that we use a segment having a start node being part of an intersection.
Referring firstly to FIGS. 5 and 6, it is in all cases necessary to find the start of the deviation, indicated at 76. FIG. 6 illustrates the simplest case in which the deviation starts before the last segment stored as part of part of the shortest route list and also forming part of the original location path list. The total location path to be described is represented by segments A, B, C, D, E, F and G. The shortest path thus far determined with certainty and coinciding with the location is represented by the segments A and D, emboldened in the Figure. As the shortest path search progresses, particularly as between the start segment A and the end node of segment E, a deviation H is found which is shorter. In such a case (which will be the most common case), ideally it is desired to find the segment appearing on the location and having a start node at which the deviation starts. In this case, segment C is required to be included as the proper intermediate as this ensures that the location is followed in any shortest path algorithm conducted in a decoding process. This search effectively recurses through the location path list for segments that meet this criteria, and this is referenced at 78, 79 in FIG. 5. Although not possible in terms of the simple path shown in FIG. 6, it is possible that no such segment may be found. In this case, the segment last stored in the shortest route list can be used as the intermediate, as illustrated at 80 as a shortest path function using the last stored segment as its start will never identify any deviation originating before it.
In an alternative embodiment, the deviation originates after the end of the last segment stored in the route search list E, as emboldened in FIG. 7. In this case the shortest path from A to E is known, and only segments between A and E have been stored. The shortest path between segment A and the end node of segment F can actually be referenced by only A and I, the latter being a deviation from the location path which includes F and occurring after the end of the last stored segment E. In this case, the intermediate can be created from that segment F, as indicated at 82 in FIG. 5, provided that the predecessor pointer for segment F actually points back to a segment on the location, in this case E. This check is indicated at 84.
In the exceptional case in FIG. 8, where the predecessor pointer for a deviation occurring after the last segment stored as part of the shortest route search actually refers back to a segment not forming part of the location, as in the case of the segment K referring back to segment J, then as a first step, a first intermediate segment E is created (as in 82 previously discussed), and a second intermediate segment D is also stored as this is the last segment occurring on the location path and beginning with an intersection from which the shorter path segment J originated. These steps are indicated generally at 86, 88 in FIG. 5, and are necessary because the stored location reference must ultimately avoid both segments J and K.
Referring finally back to FIG. 3, once the processing of the entire location path list is complete, then all the partial shortest paths identified are combined at step 46. The coverage of the location may consist of several calculated partial routes if the initial route calculation determines an intermediate segment. This intermediate segment acts as additional information in the location reference in order to guide the route search for a complete coverage of the location. If the route search reaches the end of the location all calculated partial routes will be combined to form a path which covers the location completely. This step may in one embodiment also add the expansions at the start and the end of the location as calculated in steps 36, 38 illustrated in FIG. 2. The first and last location reference points will be adjusted and new offsets describing the relative position of the original location are calculated.
To provide a better understanding of the manner in which a location is encoded in accordance with the present invention, a further specific example is provided with reference to FIGS. 9, 10, 11 and 12.
An encoder map is shown in FIG. 9 and consists of 15 nodes and 23 lines (two-way lines are counted twice). The nodes are numbered from 1 to 15. The necessary line attributes are shown beside every line using the format: <FRC>, <FOW>, <Length in meter>. FRC is an abbreviation for “Functional Road Class” and FOW is an abbreviation for “Form of Way”, both of which are described in greater detail below. The arrowheads indicate the possible driving direction for each line.
The location to be encoded is shown in FIG. 10 using bold lines. The location starts at node (3) and continues over the nodes (5), (7), (10), (11), (13), (14) and ends at node (15). Its total length in the encoder map is 685 meters. The ordered list of lines and the map to be used during encoding serves as input for the encoder.
Encoding:
In the first step of the encoding process the location will first be checked for validity. Since the location is connected and drivable and all functional road classes along the location are between 0 and 7, this location is valid. Turn restrictions are not included in the map data and therefore the encoder can ignore this check.
The encoder second step is to check the start and end node of the location as being real nodes according to certain predetermined data format rules. The end node (15) has only one incoming line and is therefore valid. The start node (3) also has two incident lines but here it is one outgoing and one incoming line. Therefore this node is not valid and the encoder searches for a real node outside the location. The encoder will find node (1) to be a real node and it also expands the location uniquely. Node (1) is chosen as the new start node for the location reference and there will be a positive offset of 150 meters. The total length of the location reference path results in 835 meters.
The third step of encoder is to proceed to calculate a shortest-path between the start line (in this case, the line between nodes (1) and (3); however, in common usage, the shortest path may be calculated without extensions) and the end line (line between nodes (14) and (15)) of the location. The resulting shortest-path is outlined in FIG. 11 using bold lines. The shortest-path has a length of 725 meters.
The next (fourth) step of the encoding process is now to check whether the location is covered by the calculated shortest-path. It will determine that this is not the case and there is a deviation after node (10).
According to the principles outlined above, the encoder will determine the line from node (10) to (11) as becoming a new intermediate location reference point. Node (10) is a real node since it cannot be stepped over during route search and the shortest-path to this line covers the corresponding part of the location completely. The length of the location being covered after this first shortest-path calculation is 561 meters.
The next encoding step prepares the route calculation in order to determine a shortest-path for the remaining part of the location (from node (10) over (11), (13) and (14) to (15)). The shortest-path calculation will therefore start at the line from (10) to (11) and ends at the line from (14) to (15).
The encoder returns to step 3 above and will determine a shortest path (length: 274 meters) between (10) and (15) and step 4 above will return that the location is now completely covered by the calculated shortest paths.
As a next step, the location reference path will be composed of the two shortest-paths and the ordered list of location reference points will now be formed. FIG. 12 shows the lines in bold which are selected for the location reference points. The first location reference point points to the line from node (1) to (3) and indicates the start of the location reference path, the second location reference point points to the line from node (10) to (11) and this line was necessary to avoid the deviation from the location. The last location reference point points to the line from node (14) to (15) and indicates the end of the location reference path.
The penultimate step is a check of the validity of the location reference. Since all lengths between two subsequent location reference points are less than the maximum distance, the location reference is confirmed as being valid.
The final step is the conversion of the ordered list of LRPs into a binary location reference.
It will therefore be appreciated from the above that the encoding process (and also the decoding process) is based on route search algorithms which investigate the lines stored in map databases. Typically a goal-directed unidirectional search, such as A*, is used to determine the shortest path coverage of a line location. While the number of lines that need to be investigated is already reduced through the use of e.g. A* algorithm, it would be desirable to further enhance the encoding method as described above.